//给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。 
//
// （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。） 
//
// 返回 A 中好子数组的数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：A = [1,2,1,2,3], K = 2
//输出：7
//解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
// 
//
// 示例 2： 
//
// 
//输入：A = [1,2,1,3,4], K = 3
//输出：3
//解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 20000 
// 1 <= A[i] <= A.length 
// 1 <= K <= A.length 
// 
// Related Topics 数组 哈希表 计数 滑动窗口 👍 319 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.HashMap;

/**
 * Java：K 个不同整数的子数组
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P992_SubarraysWithKDifferentIntegers {
    public static void main(String[] args) {
        Solution solution = new P992_SubarraysWithKDifferentIntegers().new Solution();
        // TODO 此处开始你的表演
        int count = solution.subarraysWithKDistinct(MyUtil.createArray(1, 2, 1, 2, 3), 2);
        System.out.println(count);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int subarraysWithKDistinct(int[] nums, int k) {
            // 数组长度不可小于k
            if (nums == null || nums.length < k) {
                return 0;
            }
            int sum = 0;
            // k-1种数的窗口
            Info lessK = new Info(nums, k - 1);
            // k种数的窗口
            Info equaleK = new Info(nums, k);
            for (int i = 0; i < nums.length; i++) {
                lessK.add(i);
                equaleK.add(i);
                sum += lessK.leftIndex - equaleK.leftIndex;
            }
            return sum;
        }

        private class Info {
            int[] nums;
            int k;
            // 词频记录
            HashMap<Integer, Integer> countMap;
            // 最左位置
            int leftIndex;

            public Info(int[] nums, int k) {
                this.nums = nums;
                this.k = k;
                countMap = new HashMap<>();
                leftIndex = 0;
            }

            /**
             * 窗口右移一位同时根据k值调整最左位置
             *
             * @param index 增加的坐标
             */
            public void add(int index) {
                int value = nums[index];
                Integer count = countMap.get(value);
                countMap.put(value, count == null ? 1 : count + 1);
                // 需要调整了
                while (countMap.keySet().size() > k) {
                    int leftIndexValue = nums[leftIndex++];
                    Integer num = countMap.get(leftIndexValue);
                    if (num == 1) {
                        countMap.remove(leftIndexValue);
                    } else {
                        countMap.put(leftIndexValue, num - 1);
                    }
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}